package basic.study.algorithms.struct.BST.Balanced;

import basic.study.algorithms.struct.BST.TreeNode;

/**
 * @author Kevin
 * @date 2020/3/6 19:26
 */
public class Judge_balanced {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;

        int left = maxDepth(root.left);//左子树最大深度
        int right = maxDepth(root.right);//右子树最大深度
        if (Math.abs(left - right) > 1) {
            return false;
        }
        if (isBalanced(root.left)) {
            return true;
        }
        return isBalanced(root.right);//检验两边情况，是怕极端个例，比例： “人”字型的
    }

    public int maxDepth(TreeNode node) {
        if (node == null) return 0;

        return Math.max(maxDepth(node.left), maxDepth(node.right))+1;
    }
}
